/*
*
给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。

请你返回在网格图中从 任意 格子出发，达到 任意 格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 109 + 7 取余 后返回。

如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

示例 1：

输入：grid = [[1,1],[3,4]]
输出：8
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[1]，[3]，[4] 。
- 长度为 2 的路径：[1 -> 3]，[1 -> 4]，[3 -> 4] 。
- 长度为 3 的路径：[1 -> 3 -> 4] 。
路径数目为 4 + 3 + 1 = 8 。
示例 2：

输入：grid = [[1],[2]]
输出：3
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[2] 。
- 长度为 2 的路径：[1 -> 2] 。
路径数目为 2 + 1 = 3 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 105
1 <= grid[i][j] <= 105

  - @author ala
  - @date 2024-09-23 16:17
*/
package main

import "fmt"

func main() {
	//grid := [][]int{{1, 1}, {3, 4}}
	grid := [][]int{{1}, {2}}

	fmt.Println(countPaths(grid))
}

func countPaths(grid [][]int) int {
	return V1(grid)
}

var (
	MOD    int = 1e9 + 7
	POINTS     = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
)

/**
 *  1）用拓补序的方法dp
 *      假设(_i, _j)是(i,j)的邻接点，如果 grid[_i][_j] 比 grid[i][j] 小，则(i,j)点的入度+1
 *      统计所有点的入度，记录入度为0的点，作为roots点
 *  2）dp[i][j]表示走到(i,j)的路径数，遍历所有roots点
 *      如果 grid[_i][_j] < grid[i][j]，则dp[i][j] += dp[_i][_j]
 *      如果 grid[_i][_j] > grid[i][j]，则(_i, _j)点的入度-1
 *          如果(_i, _j)点的入度减到0，则(_i, _j)加入带遍历队列
 */
func V1(grid [][]int) int {
	M, N := len(grid), len(grid[0])

	//	找入度为0的点
	ins := makeInt2D(M, N)
	queue, ql, qr, qs := make([][]int, M*N), 0, -1, 0
	for i := range grid {
		for j := range grid[i] {
			//	如果 grid[_i][_j] 比 grid[i][j] 小，则(i,j)点的入度+1
			for _, p := range POINTS {
				_i, _j := i+p[0], j+p[1]
				if _i < 0 || _i == M || _j < 0 || _j == N || grid[_i][_j] >= grid[i][j] {
					continue
				}
				ins[i][j]++
			}
			if ins[i][j] == 0 {
				qr++
				qs++
				queue[qr] = []int{i, j}
			}
		}
	}

	//	从入度为0的点开始遍历
	dp, res := makeInt2D(M, N), 0
	for qs > 0 {
		_ql, _qr := ql, qr
		qs -= qr - ql + 1
		ql = qr + 1
		for _ql <= _qr {
			r := queue[_ql]
			queue[_ql] = nil
			_ql++
			i, j, v := r[0], r[1], grid[r[0]][r[1]]
			dp[i][j] = 1
			for _, p := range POINTS {
				_i, _j := i+p[0], j+p[1]
				if _i < 0 || _i == M || _j < 0 || _j == N {
					continue
				}
				_v := grid[_i][_j]

				if v > _v {
					dp[i][j] = (dp[i][j] + dp[_i][_j]) % MOD
				}
				if v < _v {
					ins[_i][_j]--
					if ins[_i][_j] == 0 {
						qr++
						qs++
						queue[qr] = []int{_i, _j}
					}
				}
			}
			res = (res + dp[i][j]) % MOD
		}
	}
	return res
}
func makeInt2D(M, N int) [][]int {
	arr := make([][]int, M)
	for i := range arr {
		arr[i] = make([]int, N)
	}
	return arr
}
